Дискретно-стохастические модели (Р-схемы).
Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S. Поскольку сущность дискретизации времени при этом подходе остается аналогичной рассмотренным в п.4.2 конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах.
В общем виде вероятностный автомат (англ. Probabilistic automat) можно определить как дискретный прокатный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано стохастически.
Применение схем вероятностных автоматов (Р-схем) имеет важное значение для разработки методов проектирования дискретных систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям.
Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (X
I, ZS), где XI и ZS – элементы входного подмножества Х и подмножества состояний Z соответственно. Если существуют две такие функции j и y , что с их помощью осуществляются отображения G® Z и G® Y, то говорят, что F=<Z,X,Y,j ,y > определяет автомат детерминированного типа.Введем в рассмотрение более общую математическую схему. Пусть Ф – множество всевозможных пар вида (
zk, уi), где уi – элемент выходного подмножества Y. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида:Элементы из F ... (z
1,y1) (z1,y2) … (z1,yJ-1) (z1,yJ)(х
i,z8) … b11 b12 … bk(J-1) bkJK J
При этом
S S bkj=1, где bkj – вероятности перезода автомата в состояниеk=1 j=1
zk
и появления на выходе сигнала yi, если он был в состоянии z8 и на его вход в этот момент времени поступил сигнал xi. Число таких распределений, представленных в вид таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P=<Z,X,Y,B> называется вероятностным автоматом (Р-автоматом).Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, что можно представить соответственно в виде:
Элементы из Y
… y1 y2 … yJ-1 yJ(xi,z8) … q1 q2 … qJ-1 qJ
Элементы из Z
… z1 z2 … zK-1 zK(xi,z8) … z1 z2 … zK-1 zK
K J
При этом
S zk =1 и S qk=1, где zk и qk – вероятности переходаk=1 k=1
Р-автомата в состояние
zk и появления выходного сигнала yk при условии, что Р-автомат находился в состоянии zs и на его вход поступил входной сигнал xi.Если для всех k и i имеет место соотношение
qk zj = bkj, то такой Р-автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.Пусть теперь определение выходного сигнала Р-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы. Другими словами, пусть каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:
Элементы из Y
… y1 y2 … yK-1 yKZK … s1 s2 … sI-1 sI
I
Здесь
S si = 1, где si - вероятность появления выходного сигнала yi приi=1
условии, что Р-автомат находился в состоянии
zk.Если для всех k и i имеет место соотношение
zk si = bki, то такой Р-автомат называется вероятностным автоматом Мура. Понятие Р-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом, задаваемым F=<Z,X,Y,j ,y >. Частным случаем Р-автомата, задаваемого как P=<Z,X,Y,B>, являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал Р-автомата определяется детерминированно, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.
Пример. Рассмотрим Y-детерминированный Р-автомат, который задан таблицей переходов 6 и таблицей выходов:
Z … z1 z2 … zK-1 zK
Y … yi1 yi2 … yiK-1 yiK
В этих таблицах
pij - вероятность перехода Р-автомата из состояния zi в состояниеK
zj
. При этом, как и ранее, S pij = 1.j=1
Первую из этих таблиц можно представить в виде квадратной матрицы размерности KxK, которую будем называть матрицей переходных вероятностей или просто матрицей переходов Р-автомата. В общем случае такая матрица переходов имеет вид
p11 p12 … p1K
Pp = p21 p22 … p2K
. . . . . .
pK1 pK2 … pKK
Таблица 6
|
Zk |
Zk |
||||
|
Z1 |
Z2 |
… |
ZK-1 |
ZK |
|
|
Z1 |
P11 |
P12 |
… |
P1(K-1) |
P1K |
|
Z2 |
P21 |
P22 |
… |
P2(K-1) |
P2K |
|
… |
… |
… |
… |
… |
… |
|
ZK |
PK1 |
PK2 |
… |
PK(K-1) |
PKK |
Для описания Y-детерминированного Р-автомата необходимо задать начальное распределение вероятностей вида:
Z … z1 z2 … zK-1 zK
D … d1 d2 … dK-1 dK
Здесь
dk – вероятность того, что в начале работы Р-автомат находится вK
состоянии
zk. При этом S dK = 1.k=1
Будем считать, что до начала работы (до нулевого такта времени) Р-автомат всегда находится в состоянии z
0 и в нулевой такт времени меняет состояние в соответствии с распределением D. Дальнейшая смена состояний Р-автомата определяется матрицей переходов Рр. Информацию о начальном состоянии Р-автомата удобно ввести в матрицу Рр, увеличив ее размерность до (К+1)(К+1). При этом первая строка такой матрицы, сопоставляемая состоянию z0, будет иметь вид (0,d1,d2,…,dk), а, первый столбец будет нулевым.Описанный Y-детерминированный Р-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги – возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода
pij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.Очевидно, что с точки зрения математического аппарата задание Y-детерминированного Р-автомата эквивалентно заданию некоторой дискретной марковской цепи с конечным множеством состояний. Поэтому аппарат марковских цепей является основным при использовании Р-схем для аналитических расчетов.
Пример. Пусть задан Y-детерминированный Р-автомат

На рис.11 показан граф переходов этого автомата. Требуется оценить суммарные финальные вероятности пребывания этого Р-автомата в состояниях z2 и z3.
При использовании аналитического подхода можно записать известные соотношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. При этом начальное состояние z
0 можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда имеем
Где
ck-финальная вероятность пребывания Р-автомата в состоянии zk.Получаем систему уравнений
с
1 = с4;с
2 = 0.75с2 + 0.40с3;с
3 = с1;с
4 = 0,25с2 + 0.60с3.Добавим к этим уравнениям условие нормировки c
1+с2+с3+с4=1. Тогда, решая систему уравнений, получим с1 = 5 / 23, с2 = 8 / 23, с3 = 5 / 23, с4 = 5 / 23. Таким образом, с2 + с3 = 0,5652. Другими словами, при бесконечной работе заданного в этом примере Y-детерминированного Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652. 
Подобные Р-автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е.
Для оценки различных характеристик исследуемых систем, представляемых в виде Р-схем, кроме рассмотренного случая аналитических моделей можно применять и имитационные модели, реализуемые, например, методом статистического моделирования.
Элементы теории массового обслуживания.
Одним из математических методов исследования стохастических сложных систем является теория массового обслуживания, занимающаяся анализом эффективности функционирования так называемых систем массового обслуживания. Работа любой такой системы заключается в обслуживании поступающего на неё потока требований или заявок. Заявки поступают одна за другой в некоторые, случайные моменты времени. Обслуживание поступившей заявки продолжается некоторое время, после чего система освобождается для обслуживания следующей заявки. Каждая такая система может состоять из нескольких функционирующих единиц, которые называют каналами обслуживания, или обслуживающими аппаратами.
Примеры систем: кассы, В.Ц., АСУ.
Математический аппарат теории массового обслуживания позволяет оценить эффективность системой заданного потока заявок в зависимости от характеристик этого потока, числа каналов системы и производительности каждого из каналов.
В качестве критерия эффективности системы обслуживания могут быть использованы различные величины и функции, например: вероятность обслуживания каждой из поступающих заявок, средняя доля обслуженных заявок, среднее время ожидания обслуживания, среднее время простоя каждого из каналов
и системы в целом, закон распределения длины очереди, пропускная способность системы и т.д.. Численное значение этих критериев характеризует способность системы выполнять поставленные перед ней задачи – удовлетворение потока поступающих в систему требований.Термин пропускная способность используется в следующем смысле – это среднее число заявок, которое система может обслужить в единицу времени. Эффективность системы обслуживания может быть оценена также относительной пропускной способностью – средним отношением числа обслуженных заявок к числу поступивших.
В силу случайного характера момента поступивших заявок процесс их обслуживания представляет собой случайный процесс. Теория массового обслуживания позволяет получить систематическое описание этого процесса, изучение которого даёт возможность оценить пропускную способность системы и дать рекомендации по рациональной организации обслуживания.
Все системы массового обслуживания имеют вполне определённую структуру (см. рис.12):

Рис.12 Структура системы массового обслуживания
В любой системе массового обслуживания имеется входящий поток, выходящий поток и собственно система обслуживания.
Поток требований, нуждающихся в обслуживании и поступающих в систему обслуживания называется входящим. Поток требований, покидающих систему ослуживания, называется выходящим. Совокупность обслуживания вместе с системой правил, устанавливающих организацию обслуживания, образуют систему обслуживания.
Входящий поток. Простейший поток и его свойства.
Поток событий называется регулярным, если события следуют одно за другим через строго определённые промежутки времени. Такие потоки редко встречаются в реальных системах, для которых типичными являются именно случайные моменты времени.
Рассмотрим случайный входящий поток, обладающий простейшими свойствами.
Введём ряд определений.
Условию стационарности удовлетворяет поток заявок, вероятностные характеристики которого не зависят от времени. Эти условия выполняются для многих реальных процессов.
Условие ординарности означает, что заявки поступают в систему по одиночке, а не парами, тройками и т.д.
Условие отсутствия последствия является наиболее существенным для простейшего потока. Выполнение этого условия означает, что заявки поступают независимо друг от друга. Поток без последствия – поток входящих в вокзал пассажиров, но выходящие обладают последствием, т.к. это связано с приходом поезда. Вообще выходящие потоки заявок, покидающих систему, обычно имеют последствие, даже если входящий поток его не имеет. Например, пусть имеется одноканальная система массового обслуживания с фиксированным временем обслуживания
tаб. Выходящий поток обладает тем свойством, что минимальный интервал времени между последовательно обслуженными заявками будет равен tаб. При этом, если в некоторый момент t1 систему покинула заявка, то можно утверждать, что на интервале (t1, t1+ tаб) обслуженных заявок больше не появится, и таким образом, имеется зависимость между числом событий на не перекрывающихся интервалах.Получим аналитическое описание простейшего потока и рассмотрим его свойства подробнее.
Рассмотрим на оси t простейший поток событий (см. рис.13), как неограниченную последовательность случайных точек. Выделим произвольный интервал времени длиной τ. Поскольку поток является простейшим то число событий, попадающих на интервал τ равен

а=λ
∙ τгде λ – плотность потока.
В соответствии с законом Пуассона (теория вероятности) вероятность того, что за время τ произойдёт m событий, равна

![]()
Тогда вероятность того, что не произойдёт события, будет:
![]()
Отсюда вероятность того, что за время τ произойдёт хотя бы одно событие равна
![]()
Важнейшей характеристикой потока является закон распределения длин интервалов между событиями. Пусть Т- случайная величина и F(t)=P(T<t) – искомый закон распределения продолжительности временного интервала между последовательными событиями. P(T<t) это вероятность появления хотя бы одного события в течении временного интервала t, начинающегося в момент появления в
системе события.Поскольку простейший поток не обладает последствием, наличие события в начале интервала t не оказывает ни какого влияния на вероятность появления событий в дальнейшем. Поэтому вероятность P(T<t) может быть вычислена по формуле:
![]()
отсюда
![]()
Дифференцируя последнее выражение найдём плотность распределения длин интервалов между последовательными событиями.
![]()
Этот закон распределения называется показательным с параметром λ
.